home *** CD-ROM | disk | FTP | other *** search
/ Software Vault: The Gold Collection / Software Vault - The Gold Collection (American Databankers) (1993).ISO / cdr54 / bison118.zip / WARSHALL.C < prev   
C/C++ Source or Header  |  1993-06-01  |  3KB  |  120 lines
  1. /* Generate transitive closure of a matrix,
  2.    Copyright (C) 1984, 1989 Free Software Foundation, Inc.
  3.  
  4. This file is part of Bison, the GNU Compiler Compiler.
  5.  
  6. Bison is free software; you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation; either version 2, or (at your option)
  9. any later version.
  10.  
  11. Bison is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with Bison; see the file COPYING.  If not, write to
  18. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19.  
  20.  
  21. #include <stdio.h>
  22. #include "system.h"
  23. #include "machine.h"
  24.  
  25.  
  26. /* given n by n matrix of bits R, modify its contents
  27.    to be the transive closure of what was given.  */
  28.  
  29. void
  30. TC(R, n)
  31. unsigned *R;
  32. int n;
  33. {
  34.   register int rowsize;
  35.   register unsigned mask;
  36.   register unsigned *rowj;
  37.   register unsigned *rp;
  38.   register unsigned *rend;
  39.   register unsigned *ccol;
  40.  
  41.   unsigned *relend;
  42.   unsigned *cword;
  43.   unsigned *rowi;
  44.  
  45.   rowsize = WORDSIZE(n) * sizeof(unsigned);
  46.   relend = (unsigned *) ((char *) R + (n * rowsize));
  47.  
  48.   cword = R;
  49.   mask = 1;
  50.   rowi = R;
  51.   while (rowi < relend)
  52.     {
  53.       ccol = cword;
  54.       rowj = R;
  55.  
  56.       while (rowj < relend)
  57.     {
  58.       if (*ccol & mask)
  59.         {
  60.           rp = rowi;
  61.           rend = (unsigned *) ((char *) rowj + rowsize);
  62.  
  63.           while (rowj < rend)
  64.         *rowj++ |= *rp++;
  65.         }
  66.       else
  67.         {
  68.           rowj = (unsigned *) ((char *) rowj + rowsize);
  69.         }
  70.  
  71.       ccol = (unsigned *) ((char *) ccol + rowsize);
  72.     }
  73.  
  74.       mask <<= 1;
  75.       if (mask == 0)
  76.     {
  77.       mask = 1;
  78.       cword++;
  79.     }
  80.  
  81.       rowi = (unsigned *) ((char *) rowi + rowsize);
  82.     }
  83. }
  84.  
  85.  
  86. /* Reflexive Transitive Closure.  Same as TC
  87.    and then set all the bits on the diagonal of R.  */
  88.  
  89. void
  90. RTC(R, n)
  91. unsigned *R;
  92. int n;
  93. {
  94.   register int rowsize;
  95.   register unsigned mask;
  96.   register unsigned *rp;
  97.   register unsigned *relend;
  98.  
  99.   TC(R, n);
  100.  
  101.   rowsize = WORDSIZE(n) * sizeof(unsigned);
  102.   relend = (unsigned *) ((char *) R + n*rowsize);
  103.  
  104.   mask = 1;
  105.   rp = R;
  106.   while (rp < relend)
  107.     {
  108.       *rp |= mask;
  109.  
  110.       mask <<= 1;
  111.       if (mask == 0)
  112.     {
  113.       mask = 1;
  114.       rp++;
  115.     }
  116.  
  117.       rp = (unsigned *) ((char *) rp + rowsize);
  118.     }
  119. }
  120.